/*
 * gc.c
 *
 *  Created on: Nov 15, 2011
 *      Author: Rui Zhuang
 */

#include "gc.h"

bool g_debug = FALSE;
gc_heap_node* g_ptrHeap = NULL;
gc_root_node* g_ptrRoot = NULL;
int    g_nCurrentHeapSize = 0;

/* 1GB size limitation for heap */
int    g_nMaxHeapSize = 1*1024*1024;

void* gc_malloc(int size) {
	if(g_debug){
		printf("*** Enter gc_malloc ***\n");
	}
	void* heap;
	if (size < 0) {
		//TODO: print some hint here for user
		printf("!!! Error: parameter size should not less than 0 !!!\n");
	}

	heap = malloc(size);
	if (heap != NULL) {
		gc_add_heap_node(heap, size);
		g_nCurrentHeapSize += size;
		gc_check_heap_size();
	} else {
		/* if malloc fails, need to do garbage collection */
		printf("Exceeding the limited heap size, do garbage collection...\n");
		gc_recycle();
		heap = malloc(size);

		/* if still fails , really bad luck, reply no memory
		 * available
		 * Or: alternative can be increase the g_nMaxHeapSize here
		 * For now we assume it will not exceed the limitation of 1GB
		 */
		if (heap == NULL) {
			printf("No memory avaiable...\n");
			return NULL;
		} else {
			gc_add_heap_node(heap, size);
			g_nCurrentHeapSize += size;
			if(g_debug){
				printf("Current heap size = %d \n", g_nCurrentHeapSize);
			}
			gc_check_heap_size();
		}
	}
	if(g_debug){
		printf("*** Exit gc_malloc ***\n");
	}
	return heap;
}

void gc_add_heap_node(void* node, int size) {
	gc_heap_node* temp;
	if (g_ptrHeap == NULL) {
		g_ptrHeap = (gc_heap_node *) malloc(sizeof(gc_heap_node));
		g_ptrHeap->ptr = NULL;
		g_ptrHeap->size = 0;
		g_ptrHeap->reachable = TRUE;
		g_ptrHeap->next = NULL;
		if(g_debug){
			printf("--- Heap head created ---\n");
		}
	}
	temp = (gc_heap_node *) malloc(sizeof(gc_heap_node));
	temp->next = g_ptrHeap->next;
	temp->ptr = node;
	temp->size = size;
	temp->reachable = FALSE;
	g_ptrHeap->next = temp;
	if(g_debug){
		printf("<<< new heap node added with size = %d >>>\n", size);
	}
	return;
}



//check whether the heap size limit is reached
//heap size limit is reset to 0 each time gc_recycle is called
void gc_check_heap_size() {
	if(g_debug){
		printf("*** Enter gc_check_heap_size ***\n");
	}
	if (g_nCurrentHeapSize >= g_nMaxHeapSize) {
		if(g_debug){
			printf("Heap overflow, now try to do gc_recycle!\n");
		}
		gc_recycle();
		g_nCurrentHeapSize = 0;
	}
	if(g_debug){
		printf("*** Exit gc_check_heap_size ***\n");
	}
}

void gc_check_heap_node_reachable(gc_heap_node* cur_heap_node) {
	if (!(cur_heap_node->reachable)) {
		cur_heap_node->reachable = TRUE;
		/* start to consider the object of cur_heap_node pointed to */
		void* objectStartAddr = cur_heap_node->ptr;
		void* objectEndAddr = objectStartAddr + cur_heap_node->size - 4;
		while (objectStartAddr <= objectEndAddr) {
			/* check if there are some other heap node point to the address
			 * between objectStartAddr and objectEndAddr, if there are then
			 * means current object has some referenced field
			 */
			gc_heap_node* temp_heap_node = g_ptrHeap->next;
			while (temp_heap_node != NULL) {
				if(!(temp_heap_node->reachable) && ((temp_heap_node->ptr) == *(void**)objectStartAddr)){
					temp_heap_node->reachable = TRUE;
					gc_check_heap_node_reachable(temp_heap_node);
				}
				temp_heap_node = temp_heap_node->next;
			}
			objectStartAddr++;
		}
	}
}

void gc_recycle() {
	if(g_debug){
		printf("*** Enter gc_recycle *** \n");
		printf("  Before mark and sweep phase \n");
		printf("  Output root nodes info \n\n");
		gc_output_root_nodes();
		printf("  Output heap nodes info \n\n");
		gc_output_heap_nodes();
	}
	if(g_ptrHeap == NULL || g_ptrRoot == NULL){
		if(g_debug){
			printf("No heap or root nodes have been mallocced !");
		}
		return;
	}
	/* mark phase */
	gc_mark();
	/* sweep phase */
	gc_sweep();
	if(g_debug){
		printf("  After mark and sweep phase \n");
		printf("  Output root nodes info \n\n");
		gc_output_root_nodes();
		printf("  Output heap nodes info \n\n");
		gc_output_heap_nodes();
		printf("*** Exit gc_recycle *** \n");
	}
}

void gc_mark() {
	if(g_debug){
		printf("*** Enter gc_mark phase ***\n");
	}
	gc_heap_node* cur_heap_node = g_ptrHeap->next;
	/* first set all the heap node reached to false */
	while (cur_heap_node != NULL) {
		cur_heap_node->reachable = FALSE;
		cur_heap_node = cur_heap_node->next;
	}
	/*
	 * then we start to set the reached to true, which also
	 * makes the owning object to be unscanned that means
	 * this object we have determined it to be reached but its
	 * successors we have not considered yet.
	 */
	/*
	 * consider all the root nodes as unscanned
	 */
	cur_heap_node = g_ptrHeap->next;
	while(cur_heap_node != NULL){
		gc_root_node* unscanned = g_ptrRoot->next;
		while (unscanned != NULL) {
			int* objectAddr = unscanned->ptr;
			if ((*objectAddr) == (int)(cur_heap_node->ptr)) {
				/* check if this heap node reached or not */

				/* if not reached we should set it to reached and check if
				 * there are any other heap node reachable from this node
				 */
				gc_check_heap_node_reachable(cur_heap_node);

			}
			unscanned = unscanned->next;
		}
		cur_heap_node = cur_heap_node->next;
	}
	if(g_debug){
		printf("*** Exit gc_mark phase ***\n");
	}
}

void gc_sweep() {
	if(g_debug){
		printf("*** Enter gc_sweep phase ****\n");
	}
	gc_heap_node* cur_heap_node ;
	cur_heap_node = g_ptrHeap->next;
	while(cur_heap_node != NULL){
		gc_heap_node* temp = cur_heap_node->next;
		if(!(cur_heap_node->reachable)){
			gc_free_heap_node(cur_heap_node);
		}
		cur_heap_node = temp;
	}
	if(g_debug){
		printf("*** Exit gc_sweep phase ****\n");
	}
}

void gc_free_heap_node(gc_heap_node* heap_node_garbage) {
	/* release the object this heap node points to */
	free(heap_node_garbage->ptr);
	/* release the heap node itself */
	gc_heap_node* cur_heap_node;
	gc_heap_node* prev_heap_node;
	cur_heap_node = g_ptrHeap->next;
	prev_heap_node = g_ptrHeap;
	while(cur_heap_node != NULL){
		if(cur_heap_node == heap_node_garbage){
			prev_heap_node->next = cur_heap_node->next;
			free(cur_heap_node);
			break;
			//is that possible we have a cycle here?


		}else{
			cur_heap_node = cur_heap_node->next;
			prev_heap_node = prev_heap_node->next;
		}
	}
}

void gc_add_root_node(void* ptr){
	if(g_ptrRoot == NULL){
		g_ptrRoot = (gc_root_node*)malloc(sizeof(gc_root_node));
		g_ptrRoot->ptr = NULL;
	}
	gc_root_node* cur_root_node = (gc_root_node*)malloc(sizeof(gc_root_node));
	cur_root_node->ptr = ptr;
	cur_root_node->next = g_ptrRoot->next;
	g_ptrRoot->next = cur_root_node;
}

void gc_free_root_node(void* ptr){
	gc_root_node* cur_root_node;
	gc_root_node* prev_root_node;
	cur_root_node = g_ptrRoot->next;
	prev_root_node = g_ptrRoot;
	while(cur_root_node != NULL){
		if(cur_root_node->ptr == ptr){
			prev_root_node->next = cur_root_node->next;
			free(cur_root_node);
			cur_root_node = prev_root_node->next;
		}else{
			cur_root_node = cur_root_node->next;
			prev_root_node = prev_root_node->next;
		}
	}
}

void gc_output_root_nodes(){
	if(g_ptrRoot == NULL){
		printf("Root is null \n");
		return;
	}
	gc_root_node* cur_root_node = g_ptrRoot->next;
	int count = 0;
	while(cur_root_node != NULL){
		count++;
		printf("-------- Root node %d --------\n",count);
		printf("|      ptr = %d      |\n", *((int*)cur_root_node->ptr));
		printf("------------------------------\n\n");
		cur_root_node = cur_root_node->next;
	}
}

void gc_output_heap_nodes(){
	if(g_ptrHeap == NULL){
		printf("Heap is null \n");
		return;
	}
	gc_heap_node* cur_heap_node = g_ptrHeap->next;
	int count = 0;
	while(cur_heap_node != NULL){
		count++;
		printf("-------- Heap node %d --------\n", count);
		printf("|      ptr  = %d     |\n", (int)(cur_heap_node->ptr));
		printf("|      size = %d             |\n", cur_heap_node->size);
		printf("|      reachable = %d        |\n", cur_heap_node->reachable);
		printf("------------------------------\n\n");
		cur_heap_node = cur_heap_node->next;
	}
}
